home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _bb_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  2.0 KB  |  85 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _bb_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/impl/bb_tree.h>
  18.  
  19.  
  20. void bb_tree::rebal(bb_tree_item v, int delta)
  21. {
  22.   while ( v != root() )
  23.   { 
  24.     bb_tree_item u = v->parent;
  25.     bb_tree_item l = u->child[left];
  26.     bb_tree_item r = u->child[right];
  27.  
  28.     int bu  = u->get_bal() + delta;      // increase/decrease weight of u
  29.     int bl  = l->get_bal();
  30.     int br  = r->get_bal();
  31.  
  32.     u->set_bal(bu);
  33.  
  34.     if (64*bl < bu*alpha)
  35.        { int brl = r->child[left]->get_bal();
  36.          if (64*brl <=  d * br) 
  37.             { rotation(u,r,right);
  38.               r->set_bal(bu);
  39.               u->set_bal(bl + brl);
  40.               v = r;
  41.              }
  42.          else 
  43.             { bb_tree_item w = r->child[left];
  44.               int bwl = w->child[left]->get_bal();
  45.               double_rotation(u,r,w,right);
  46.               w->set_bal(bu);
  47.               u->set_bal(bl + bwl);
  48.               r->set_bal(br - bwl);
  49.               v = w;
  50.              }
  51.         }
  52.     else 
  53.        if (64*br < bu*alpha) 
  54.        { int bll = l->child[left]->get_bal();
  55.          if (64*bll >  d * bl) 
  56.               { rotation(u,l,left);
  57.                 l->set_bal(bu);
  58.                 u->set_bal(bu - bll);
  59.                 v = l;
  60.                }
  61.        else 
  62.               { bb_tree_item w = l->child[right];
  63.                 int bwr = w->child[right]->get_bal();
  64.                 double_rotation(u,l,w,left);
  65.                 w->set_bal(bu);
  66.                 u->set_bal(br + bwr);
  67.                 l->set_bal(bl - bwr);
  68.                 v = w;
  69.                }
  70.         }
  71.  
  72.         else v = u;
  73.        
  74.    }
  75.  
  76. }
  77.  
  78.  
  79.  
  80. void bb_tree::insert_rebal(bb_tree_item v) { rebal(v,1); }
  81.  
  82. void bb_tree::del_rebal(bb_tree_item v, bb_tree_item) { rebal(v,-1); }
  83.  
  84.  
  85.